/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;

void reverseList(ListNode* plist, int cnt, ListNode** head)
{
    if (!plist)
        return;

    ListNode* n1 = NULL, * n2 = plist, * n3 = plist;

    while (cnt && n3)
    {
        n3 = n2->next;
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        cnt--;
    }

    *head = n1;
    plist->next = n3;
}

ListNode* reverseBetween(ListNode* head, int left, int right)
{
    if (right == left)
        return head;

    ListNode* pcur = head;
    ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
    phead->next = head;
    ListNode* pre = phead;
    int cnt = 1;

    while (pcur)
    {
        if (cnt == left)
        {
            ListNode* h = NULL;
            reverseList(pcur, right - left + 1, &h);
            pre->next = h;
            break;
        }
        else
        {
            pre = pcur;
            pcur = pcur->next;
            cnt++;
        }
    }

    ListNode* res = phead->next;
    free(phead);
    return res;
}